K最短路径算法之Yen算法
前几篇推送详细介绍了部分最短路径算法：
今天来介绍最短路径算法的扩展系列--K最短路径算法之Yen算法。K最短路径就是要求出前K条最短路径。例如，我们经常用的导航App会给出几条路径给用户选择，如从大雁塔到咸阳机场在百度地图上给出了3条驾车出行方案。
今天我将介绍如何通过Yen算法来计算前K条最短路径。
关于图的定义以及斐波那契堆(F堆)的定义请参考：Dijkstra算法。
K最短路径即找出第一条最短路径，第二条最短路径，...，直到第K条最短路径，且这K条最短路径是按权重之和大小排序。
先通过最短路径算法，例如Dijkstra算法、A*算法等，计算第一条最短路径，如上图中的路径P1 = {1,2,3,4}。路径P1存在三条偏离路径{a,b,c}，偏离路径是指每条路径前i个节点和路径P1一致，重合的部分称之为根路径，节点i称之为偏离节点；然后从第i个节点偏离原来的路径到达终点，偏离的路径称之为子路径，在计算之前需要先将节点i之前的节点以及第i条边（称之为偏离边）都从网络中移除掉，这样就能保证计算的子路径不包含根路径中的节点，即不存在环。如路径b前2个节点{1,2}与路径P1一致，然后从节点2偏离一条子路径(红色路径)到达终点。那么从这三条偏离路径{a,b,c}选出最小的一条作为第二条最短路径。所以我们需要一个优先队列来保存所有求得的偏离路径，每次从优先队列取出一条最小的作为第j条最短路径。
当计算第j+1条最短路径时，我们就可以从前j条最短路径的偏离路径集中获得第j+1条最短路径。在计算第j条路径的偏离路径时，第一个偏离节点可能不是第一个节点。如下图：
我们使用了Chicago路网（12982个节点&39018条边）进行实验。取K=100，并在Chicago路网中随机取了100对OD来对Yen算法进行测试。测试结果如下：